package k2;

public class Priority {
	private Dynamic priority;
	public void create(){
		priority = new Dynamic();
		priority.create(1);
	}
	public void enqueue(int x){
		priority.add(x);
		int newest = priority.len();
		int older = newest / 2;
		while(newest != 1 && priority.get(older) > x){
			int temp = priority.get(older);
			priority.put(x, older);
			priority.put(temp, newest-1);
			newest = older;
			older = newest / 2;
		}
	}
	public int dequeue(){
		int result = priority.get(1);
		priority.put(priority.rem(), 1);
		// index of parent element
		int parent = 1;
		// index of child with smaller value
		int smallerChild = getSmallerChild(parent);
		// while there is a smaller child element and parent is bigger than smaller child, swap elements
		while (smallerChild != 0 && priority.get(parent) > priority.get(smallerChild)) {
			int temp = priority.get(parent);
			priority.put(priority.get(smallerChild), parent);
			priority.put(temp, smallerChild);
			parent = smallerChild;
			smallerChild = getSmallerChild(parent);
		}
		return result;
	}
	public int getSmallerChild (int i) {
		int min = 0;
		if (priority.len() >= (i * 2)) {
			min = i * 2;
		}
		if (priority.len() >= (i * 2 + 1) && priority.get(i * 2 + 1) < priority.get(min)) {
			min = i * 2 + 1;
		}
		
		return min;
	}
	public boolean isEmpty(){
		if(priority.len() == 0) return true;
		return false;
	}
}
